from typing import List


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        done, candi, route = [], [], [] # 已有字符，树，第几个节点
        m, n = len(board), len(board[0])

        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:

                    k, x, y = 1, i, j
                    if k == len(word):
                        return True
                    done.append((x, y))
                    candi.append([(x-1, y), (x+1, y), (x, y-1), (x, y+1)])
                    route.append(0)
                    while k < len(word):
                        if route == []:
                            break

                        while route[-1] < 4:
                            c = candi[-1][route[-1]]
                            if 0<= c[0] <m and 0<= c[1] <n and c not in done and word[k]==board[c[0]][c[1]]:
                                k, x, y = k+1, c[0], c[1]
                                if k == len(word):
                                    return True
                                done.append((x, y))
                                candi.append([(x-1, y), (x+1, y), (x, y-1), (x, y+1)])
                                route.append(0)
                                break
                            else:
                                route[-1] += 1
                        
                        if route[-1] == 4:
                            route.pop()
                            candi.pop()
                            done.pop()
                            k -= 1
                            if len(route) > 0:
                                route[-1] += 1
        
        return False
    
if __name__ == '__main__':
    s = Solution()
    
    """ board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
    word = "ABCCED" """
    board = [["a","b"],["c","d"]]
    word = "abcd"
    print(s.exist(board,word))